/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.google.code.peersim.pastry.protocol;

import java.math.BigInteger;
import java.util.Random;
import peersim.core.CommonState;

/**
 * A Pastry identifier is a 128-bit value ranging from 0 to 2^(128)-1.
 * Identifiers are both randomly assigned to nodes upon joining the system, and
 * used to identify resources that must be stored and located in the system.
 * Every Pastry identifier is thought of as a sequence of digits with base {@code 2^b},
 * where {@code b} is one of Pastry's configuration parameters.
 *
 * @author frusso
 * @version 0.1
 * @since 0.1
 */
public class PastryId implements Comparable<PastryId> {

  /**
   * Number of bits composing a Pastry identifier.
   */
  private final static short BITS = 128;
  /**
   * Padding character used when generating ID string-representations.
   */
  private final static char PADDING = '0';
  /**
   * The actual Pastry identifier.
   */
  private final BigInteger id;
  /**
   * Pastry's {@code b} configuration parameter.
   */
  private final int b;
  /**
   * Stores the length an ID string-representation must have.
   */
  private final int forRoutingIdLength;
  /**
   * The string representation of the ID using the given base for routing.
   */
  private final String forRouting;
  /**
   * Lazily initialized cached hashCode
   */
  private int hashCode;
  /**
   * Radix used to represent an id as string.
   */
  private final int radix;
  /**
   * Useful reference to the {@link PastryNode} instance associated with this identifier.
   */
  private final PastryNode node;

  /**
   * Package-local factory-method meant only for testing.
   *
   * @param b
   * @return
   */
  static final PastryId forTesting(int b, Random r) {
    return new PastryId(b, r, null);
  }

  /**
   * Factory-method for instantiating new {@link PastryId} instances.
   *
   * @param b Pastry's {@code b} configuration parameter
   * @param node The node this identifier refers to
   * @return
   */
  public final static PastryId newId(int b, PastryNode node) {
    return new PastryId(b, CommonState.r, node);
  }

  /**
   * Private constructor used by static factory methods.
   *
   * @param b Pastry's {@code b} configuration parameter.
   * @param prng Pseudo random number generator for the ID generation
   */
  private PastryId(int b, Random prng, PastryNode node) {
    // randomly generate a value in the [0..2^(BITS)-1] range
    id = new BigInteger(BITS, prng);
    // saves Pastry's b parameter
    this.b = b;
    // derive the String representation in the base given for routing of the id, adding
    // some leading zeros (PADDING) should the ID be not enough long
    forRoutingIdLength = BITS / b;
    // the string representation in base "radix"
    radix = Double.valueOf(Math.pow(2, b)).intValue();
    String tmpStringId = id.toString(radix);
    // padding (if requried)
    int distance = forRoutingIdLength - tmpStringId.length();
    if(distance>0) {
      StringBuilder sb = new StringBuilder(tmpStringId);
      for(int i=0; i<distance; i++) {
        sb.insert(0, PADDING);
      }
      tmpStringId = sb.toString();
    }
    forRouting = tmpStringId;
    this.node = node;
  }

  /**
   * Returns the absolute value of the difference {@code this - other}.
   *
   * @param other
   * @return The absolute value of the difference {@code this - other} or {@code null} if {@code other} is {@code null}
   */
  final BigInteger absDistance(PastryId other) {
    if(other==null) return null;
    return this.id.subtract(other.id).abs();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public final int compareTo(PastryId o) {
    return this.id.compareTo(o.id);
  }

  /**
   * Returns the value of the difference {@code this - other}.
   *
   * @param other
   * @return The value of the difference {@code this - other} or {@code null} if {@code other} is {@code null}
   */
  final BigInteger distance(PastryId other) {
    if(other==null) return null;
    return this.id.subtract(other.id);
  }

  /**
   * Two {@link PastryId}s are equal iff:<br>
   * <ol>
   * <li>they have the same numeric value expressed in base 10</li>
   * </ol>
   *
   * {@inheritDoc}
   */
  @Override
  public final boolean equals(Object obj) {
    if(this==obj)
      return true;
    if(!(obj instanceof PastryId))
      return false;
    PastryId other = (PastryId) obj;
    return this.id.equals(other.id);
  }

  /**
   * Returns this instance's first non matching char when compared to {@code other}.
   * If {@code this} does not share any prefix with {@code other}, {@code this}'
   * char of index 0 is returned.<br>
   * If {@code this} shares its full representation with {@code other}, {@code null}
   * is returned.<br>
   * Otherwise, the first non matching char is returned.
   *
   * @param other The other {@link PastryId}
   * @return The first non matching char or {@code null}
   */
  final Character firstNonMatchingChar(PastryId other) {
    Character c = null;
    int prefixLength = other.sharedPrefixLength(this);
    if(prefixLength>0) {
      if(prefixLength==this.forRouting.length()) {
        c = this.forRouting().charAt(prefixLength-1);
      } else {
        c = this.forRouting().charAt(prefixLength);
      }
    } else {
      c = this.forRouting.charAt(0);
    }
    return c;
  }

  /**
   * Returns this instance's first non matching char numerical value, as defined
   * by {@link Character#digit(char, int)}, when compared to {@code other},
   * according to what described for
   * {@link PastryId#firstNonMatchingChar(com.google.code.peersim.pastry.protocol.PastryId)}.
   *
   * @param other The other {@link PastryId}
   * @return The first non matching char numerical value or {@code null}
   */
  final Integer firstNonMatchingCharDigit(PastryId other) {
    Integer res = null;
    Character c = firstNonMatchingChar(other);
    if(c!=null)
      res = Character.digit(c, radix);
    return res;
  }

  /**
   * Returns this {@link PastryId} {@link String} representation useful for routing purposes.
   *
   * @return Representation useful for routing purposes
   */
  final String forRouting() {
    return forRouting;
  }

  /**
   * Returns Pastry's {@code b} configuration parameter.
   * 
   * @return Pastry's {@code b} configuration parameter
   */
  final int getB() {
    return b;
  }
  
  /**
   * Returns the expected length of Pastry identifiers represented in radix
   * {@code 2^b}.
   * 
   * @return the expected length of Pastry identifiers represented in radix
   * {@code 2^b}
   */
  final int getForRoutingLength() {
    return forRoutingIdLength;
  }

  /**
   * Returns the {@link PastryNode} instance this identifier refers to.
   *
   * @return The {@link PastryNode} instance this identifier refers to
   */
  final PastryNode getNode() {
    return node;
  }

  /**
   * Returns the value of {@code 2^b}.
   *
   * @return The value of {@code 2^b}
   */
  final int getRadix() {
    return radix;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public final int hashCode() {
    int res = hashCode;
    if(res==0) {
      res = 17;
      res = 31*res + id.hashCode();
      hashCode = res;
    }
    return res;
  }

  /**
   * Tells if this instance is greater than {@code other}.
   *
   * @param other
   * @return {@link Boolean#TRUE} iff this &gt; other, {@link Boolean#FALSE} otherwise
   */
  final boolean isGreaterThan(PastryId other) {
    return this.compareTo(other)>0;
  }

  /**
   * Tells if this instance is greater than or equal to {@code other}.
   *
   * @param other
   * @return {@link Boolean#TRUE} iff this &gt;= other, {@link Boolean#FALSE} otherwise
   */
  final boolean isGreaterThanOrEquals(PastryId other) {
    return this.compareTo(other)>=0;
  }

  /**
   * Tells if this instance is less than {@code other}.
   *
   * @param other
   * @return {@link Boolean#TRUE} iff this &lt; other, {@link Boolean#FALSE} otherwise
   */
  final boolean isLessThan(PastryId other) {
    return this.compareTo(other)<0;
  }

  /**
   * Tells if this instance is less than or equal to {@code other}.
   *
   * @param other
   * @return {@link Boolean#TRUE} iff this &lt;= other, {@link Boolean#FALSE} otherwise
   */
  final boolean isLessThanOrEquals(PastryId other) {
    return this.compareTo(other)<=0;
  }

  /**
   * This method reports the length of the commonly shared prefix between
   * this {@link PastryId} for-routing representation and the one of {@code other}.
   *
   * @param other
   * @return The length of the commonly shared prefix
   */
  final int sharedPrefixLength(PastryId other) {
    int len = 1;
    while(this.forRouting.regionMatches(0, other.forRouting, 0, len)) len++;
    len--;
    return len;
  }

  /**
   * The returned format foresees the numeric-representation followed by the
   * one used for routing purposes, that is the one expressed in radix {@code 2^b}.
   *
   * {@inheritDoc}
   * @return
   */
  @Override
  public final String toString() {
    return this.id.toString()+" ("+forRouting+")";
  }

  /**
   * Base 10 representation of the current {@link PastryId}.
   *
   * @return This ID base 10 representation
   */
  final BigInteger value() {
    return id;
  }
}